import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

public class huffman {
	fastIntArray fastArray;
	fastIntArray codeFreqArray;
	arrayTree tree = new arrayTree(null);
	FileOps comp, decomp;
	binaryOps bop = new binaryOps(4);
	
	int colCount = 0;
	int treesleft = 0;
	TreeNode trees[];
	TreeNode rootNode;
	long startTime = 0;
	long taskTime =0;
	String timerId;
	q theq = new q();
	PriorityQueue<TreeNode> altQ = new PriorityQueue<TreeNode>();
	int numNodes = 0;
	
	int codeSize;
	TreeNode onesToMerge[] = new TreeNode[2];
	String inFileName, outFileName;


	huffman(String act,String f1, String f2) throws IOException {
		codeSize = 2;
		if (act.contains("c")) {
			System.out.println("Compressing...");
			compress(f1,f2);
		}
		if (act.contains("d")) {
			System.out.println("Decompressing....");
			decompress(f1,f2);	
		}
		if (act.contains("r")) {
			huffman co = new huffman("c",f1,(f1.concat(".compr")));
			huffman dc = new huffman("d",(f1.concat(".compr")),f2);
		}
	}
	void compress(String ifile, String ofile) throws IOException {
		int arraySize = 1;
		arraySize = arraySize << ((codeSize * 8) ); // calculates the max number of different values for code size
		codeFreqArray = new fastIntArray(arraySize,arraySize); //where the code frequencies are stored
		for(int i=0; i < arraySize; i++) codeFreqArray.add(i, 0); //make sure not added ones all zero
		comp = new FileOps(ifile,ofile); //new file input
		outFileName = ofile; 
		try {
			setupTrees(ifile); //setup the tree nodes
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		treesleft = trees.length;
		startTimer("Adding to Q");
		for (int i=0; i < trees.length; i++) {
        //adds to the queue the initial nodes from the
        //building of the tree, so that they can be put
        //in the priority queue untill they are all merged
        //by frequencey and left with just the root node
			altQ.add(trees[i]);
		}
		//trees = null;
		System.out.println("Tress null");
		endTimer();
		startTimer("Running while stuff in q");
		TreeNode tpa[];
		while(altQ.size() > 1) {
        //this function continues to merge
        // the nodes untill the queue has
        // one node left
			tpa = new TreeNode[2];
			tpa[0] = altQ.remove();
			tpa[1] = altQ.remove();
			altQ.add(merge(tpa));
		}
		endTimer();
      //get the root node
		rootNode = altQ.remove();
		tree.setRoot(rootNode);
		startTimer("Outputting to file");
		//call the file ops to output code table and compress
      comp.compress(tree);
      //end timer and print how long it took
		endTimer();
		System.out.println("Done!");
	}
	void decompress(String inf, String outf) throws IOException {
   // calls the file ops decompress functions
		startTimer("It took this long to decompress: ");
		decomp = new FileOps(inf,outf);
		decomp.decompress();
		endTimer();
		System.out.println("Done!");
		
	}
	
	TreeNode merge(TreeNode[] a) {
   /* Merges Nodes for the builidng of a tree*/
		TreeNode newTree = new TreeNode(null,0,0);
		numNodes++;
		newTree.freq = a[0].freq + a[1].freq;
		newTree.left = a[0];
		newTree.right = a[1];
		a[0].parent = newTree;
		a[1].parent = newTree;
		return newTree;
	}
	TreeNode qMerge() {
   /* the new quick merge function, implemented to 
     * speed up performance */
     
		TreeNode newTree = new TreeNode(null,0,0);
		numNodes++;
		newTree.freq = onesToMerge[0].freq + onesToMerge[1].freq;
		newTree.left = onesToMerge[0];
		newTree.right = onesToMerge[1];
		onesToMerge[0].parent = newTree;
		onesToMerge[1].parent = newTree;
		return newTree;
	}
	void setupTrees(String inputFileName) throws IOException {
		/*
		 * This function does the following:
		 * 1. Load the file into memory
		 * 2. create a TreeNode for each possible character (i.e. A-Z)
		 * 3. Calculate the Frequency through out the file for each 
		 * 		possible character and assign it to the characters 
		 * 		respective node
		 * Store the trees in trees[]
		 */
		FileInputStream in = null;
		inFileName = inputFileName;
        int c1 = 0;
        try {
            in = new FileInputStream(inputFileName);
            byte input[] = new byte[codeSize];
            startTimer("Reading File");
            int arval;  //needed so the value from the array is not
            // initialized in each loop to save time. it holds the value 
            // from the array (arval)
            
            int codeFreqVal; //the number of times (frequency) of the specific arval
            long fileSize = in.available(); //for the progress bar, it must know the file size
	    	long byteCount = 0; //how many bytes have been read so far
	    	int intervalCount = 0; // for the progess bar- how many "bars" to show
	    	long interval = fileSize / 100; //so it knows when to add another bar to progess
	    	System.out.println("Reading the file to be compressed");
	    	comp.setupProgressBar(); //setup progess bar
            while ((in.read(input)) != -1) { //while there is still data
            	byteCount += codeSize; //number of bytes read increases
			  	if(byteCount >= (interval * intervalCount)) { //if the progess bar needs to be updated
			  		comp.printProgressBar(intervalCount); //print progress bar
			  		intervalCount++; //know how many bars have been printed
			  	}
            	arval = bop.integerFromBytes(input); //read the code from the file
            	codeFreqVal = codeFreqArray.get(arval); //get the current frequency of the code
            	if(codeFreqVal == 0) c1++; //if its 0, then its a new unique code, so increases unique codes
            	codeFreqVal++; //increases the frequency
            	codeFreqArray.update(arval, codeFreqVal); //store the frequency back into the DS
            }
            endTimer();
            System.out.println("The inputCount is: " + c1);
        } catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} finally {
        	in.close();
        }
		startTimer("Setting up tree");
		trees = new TreeNode[c1];
		numNodes += c1;
		int treeCount = 0;
		int numCodes = codeFreqArray.size(); // the number of codes is the codeFreqArray size
		int codeFreq;
		for(int i=0; i < numCodes; i++) {
			codeFreq = codeFreqArray.get(i); //temp var to make tree node
			if(codeFreq != 0) { //don't waste space and add codes that don't appear
				trees[treeCount] = new TreeNode(null,codeFreq,i); //add new node with code and code freq
				trees[treeCount].isLeaf = true; //it is a leaf
				treeCount++; //number of nodes that exist
			}
		}
		codeFreqArray = null;
		endTimer();
		
	}
	
	void startTimer(String timerName) {
   //start timer function
		startTime = System.currentTimeMillis();
		timerId = timerName;
	}
	long endTimer() {
   //end timer function
		taskTime = System.currentTimeMillis() - startTime;
		System.out.println(timerId + " took: " + taskTime + " ms");
		return taskTime;
	}
	
}
